/**
 * 超时代码
 */
public class LongestPalindromicSubsequence {
    static String max="";
    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("abbdsa"));
    }
    public static int longestPalindromeSubseq(String s) {
        int[] vis=new int[s.length()];
        dfs(0,s,vis);
        return max.length();
    }
    static void dfs(int cur,String s,int[] vis){
        if(isHuiWen(getStr(s,vis))){
            max=getStr(s,vis).length()>max.length()?getStr(s,vis):max;
        }
        for(int i=cur;i<s.length();i++){
            if(vis[i]==0){
                vis[i]=1;
                dfs(i+1,s,vis);
                vis[i]=0;
            }
        }
    }
    static String getStr(String s,int[] vis){
        String t="";
        for (int i=0;i<s.length();i++) {
            if(vis[i]==1){
                t=t+s.substring(i,i+1);
            }
        }
        return t;
    }
    static boolean isHuiWen(String t){
        if(t.length()==0){
            return false;
        }
        char[] chars = t.toCharArray();
        int l=0,r=chars.length-1;
        while(l<=r){
            if(chars[l]!=chars[r]){
                return false;
            }else{
                l++;
                r--;
            }
        }
        return true;
    }
}
